from collections import deque

from .puzzle8_state import Puzzle8State


class Puzzle8Solver():
    def __init__(self):
        self.goal_state = None;
        self.origin_state = None
        self.move_seqs = []
        self.move_history_state = []

    def solve(self, origin_state, final_state):
        pass

    def expand_state(self, cur_state):
        neighbor_states = []

        cur_state_list = cur_state.get_cur_list()

        neighbor_states.append(Puzzle8State(self.move_state(cur_state_list, 1), cur_state, 1))
        neighbor_states.append(Puzzle8State(self.move_state(cur_state_list, 2), cur_state, 2))
        neighbor_states.append(Puzzle8State(self.move_state(cur_state_list, 3), cur_state, 3))
        neighbor_states.append(Puzzle8State(self.move_state(cur_state_list, 4), cur_state, 4))

        valid_neighbour_states = [neighbor for neighbor in neighbor_states if neighbor.get_cur_list()]

        return valid_neighbour_states

    def move_state(self, cur_state_list, pos):
        new_state_list = cur_state_list[:]

        zero_index = new_state_list.index(0)

        if pos == 1:
            if zero_index >= 3:
                new_state_list[zero_index - 3], new_state_list[zero_index] = cur_state_list[zero_index], cur_state_list[
                    zero_index - 3]
                return new_state_list
            else:
                return None

        if pos == 2:
            if zero_index < 6:
                new_state_list[zero_index + 3], new_state_list[zero_index] = cur_state_list[zero_index], cur_state_list[
                    zero_index + 3]
                return new_state_list
            else:
                return None

        if pos == 3:
            if zero_index not in [0, 3, 6]:
                new_state_list[zero_index - 1], new_state_list[zero_index] = cur_state_list[zero_index], cur_state_list[
                    zero_index - 1]
                return new_state_list
            else:
                return None

        if pos == 4:
            if zero_index not in [2, 5, 8]:
                new_state_list[zero_index + 1], new_state_list[zero_index] = cur_state_list[zero_index], cur_state_list[
                    zero_index + 1]
                return new_state_list
            else:
                return None

        return None

    def backtrace(self):
        cur_state = self.goal_state

        if cur_state is None:
            print("this problem has no solution")
            return

        print(self.goal_state)
        print(cur_state)
        print(self.origin_state)

        while cur_state.get_cur_list() != self.origin_state.get_cur_list():
            move = cur_state.get_move()

            self.move_seqs.insert(0, move)
            self.move_history_state.insert(0, cur_state.get_cur_list())

            cur_state = cur_state.get_parent()

        self.move_history_state.insert(0, self.origin_state.get_cur_list())

        self.print_result()

    def print_result(self):
        for cur_move in self.move_history_state:
            print('*' * 20)
            self.print_list(cur_move)
            print("\n")

    def print_list(self, cur_move):
        for i in range(3):
            print(cur_move[i * 3]," ",cur_move[i*3+1]," ",cur_move[i*3+2])
        print('*'*20)

    def get_move_history_list(self):
        return self.move_history_state[:]




class BFSPuzzle8Solver(Puzzle8Solver):
    def __init__(self):
        super(BFSPuzzle8Solver,self).__init__()

    def solve(self, origin_state, final_state):
        self.origin_state = origin_state

        print("start BFS solve")

        state_explored = set()
        state_queue = deque()

        state_queue.append(origin_state)

        while state_queue:
            cur_state = state_queue.popleft()
            self.print_list(cur_state.get_cur_list())
            state_explored.add(tuple(cur_state.get_cur_list()))

            if cur_state.get_cur_list() == final_state.get_cur_list():
                print(cur_state)
                print(final_state)
                self.goal_state = cur_state
                break;

            state_list_of_neighbour = self.expand_state(cur_state)

            for state_neighbour in state_list_of_neighbour:
                if tuple(state_neighbour.get_cur_list()) not in state_explored:
                    state_explored.add(tuple(state_neighbour.get_cur_list()))
                    state_queue.append(state_neighbour)

        self.backtrace();



class DFSPuzzle8Solver(Puzzle8Solver):
    def __init__(self):
        super(DFSPuzzle8Solver,self).__init__()

    def solve(self, origin_state, final_state):
        self.origin_state = origin_state

        print("start DFS solve")

        state_explored = set()
        state_stack = list()

        state_stack.append(origin_state)

        while state_stack:
            cur_state = state_stack.pop()
            self.print_list(cur_state.get_cur_list())
            state_explored.add(tuple(cur_state.get_cur_list()))

            if cur_state.get_cur_list() == final_state.get_cur_list():
                print(cur_state)
                print(final_state)
                self.goal_state = cur_state
                break;

            state_list_of_neighbour = reversed(self.expand_state(cur_state))

            for state_neighbour in state_list_of_neighbour:
                if tuple(state_neighbour.get_cur_list()) not in state_explored:
                    state_explored.add(tuple(state_neighbour.get_cur_list()))
                    state_stack.append(state_neighbour)

        self.backtrace();


class AstarPuzzle8Solver(Puzzle8Solver):
    def __init__(self):
        pass
